package done.easy_101_200;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static java.lang.Math.abs;
import static java.lang.Math.max;

/**
 * 110. Balanced Binary Tree
 * <p>
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 * 本题中，一棵高度平衡二叉树定义为：
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
 * <p>
 * 示例 1:
 * <p>
 * 给定二叉树 [3,9,20,null,null,15,7]
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * <p>
 * 2019-03-23 5:41 PM
 **/
@Slf4j
public class BalancedBinaryTree {

    @SuppressWarnings("all")
    public boolean isBalanced(TreeNode root) {
        //190323 first
        return false;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(3,
                new TreeNode(9), new TreeNode(20,
                15, 7)); // 平衡二叉树
        //15, new TreeNode(7, 1, 2))); // 非平衡二叉树
        log.info("result:{}", isBalanced(root));
    }

}












































/*
public boolean isBalanced(TreeNode root) {
    return checkDepth(root) != -1;
}
/ **
 * 如果我们发现子树不平衡，则不计算具体的深度，而是直接返回-1。
 * 那么优化后的方法为：对于每一个节点，我们通过checkDepth方法
 * 递归获得左右子树的深度，如果子树是平衡的，则返回真实的深度，
 * 若不平衡，直接返回-1，此方法时间复杂度O(N)，空间复杂度O(H)
 * /
private int checkDepth(TreeNode root) {
    if (root==null) {
        return 0;
    }

    int left = checkDepth(root.left);
    if (left == -1) {
        return -1;
    }

    int right = checkDepth(root.right);
    if (right == -1) {
        return -1;
    }

    int diff = abs(left - right);

    if (diff > 1) {
        return -1;
    } else {
        return 1 + max(left, right);
    }
}
*/
